๋ฌธ์
Programmers - ๋ชจ๋ 0์ผ๋ก ๋ง๋ค๊ธฐ
๐ Logic
private long dfs(int node) {
visited[node] = true;
// ๋ฐฉ๋ฌธํ์ง ์์ ์์ ๋
ธ๋๊ฐ ์๋ค๋ฉด ํ์
for (int i = 0; i < adjList[node].size(); i++) {
int cur = adjList[node].get(i);
if (!visited[cur])
values[node] += dfs(cur);
}
// ๋ฐํ์ ์๋ฌ ์์ธ
// for (int n : adjList[node])
// if (!visited[n])
// values[node] += dfs(n);
long value = values[node];
answer += Math.abs(value);
return value;
}
- ๋ฆฌํ ๋ ธ๋๋ถํฐ 0์ผ๋ก ๋ง๋ ๋ค.
๐ CODE
์ฝ๋ ๋ณด๊ธฐ/์ ๊ธฐ๐ซ
import java.util.*;
class Solution {
private ArrayList<Integer>[] adjList;
private int size;
private long answer = 0;
private long[] values;
private boolean[] visited;
public long solution(int[] a, int[][] edges) {
size = a.length;
values = new long[size];
visited = new boolean[size];
adjList = new ArrayList[size];
if (init(a) != 0) return -1;
for (int[] edge : edges) {
int n1 = edge[0];
int n2 = edge[1];
adjList[n1].add(n2);
adjList[n2].add(n1);
}
dfs(0);
return answer;
}
private int init(int[] a) {
int sum = 0;
for (int i = 0; i < size; i++) {
sum += a[i];
values[i] = a[i];
adjList[i] = new ArrayList<>();
}
return sum;
}
private long dfs(int node) {
visited[node] = true;
// ๋ฐฉ๋ฌธํ์ง ์์ ์์ ๋
ธ๋๊ฐ ์๋ค๋ฉด ํ์
for (int i = 0; i < adjList[node].size(); i++) {
int cur = adjList[node].get(i);
if (!visited[cur])
values[node] += dfs(cur);
}
// ๋ฐํ์ ์๋ฌ ์์ธ
// for (int n : adjList[node])
// if (!visited[n])
// values[node] += dfs(n);
long value = values[node];
answer += Math.abs(value);
return value;
}
}
โ๏ธ Review
- ํธ๋ฆฌ๋ฅผ ๊ทธ๋ ค๋๊ณ ๋ฆฌํ ๋ ธ๋๋ถํฐ ๋ณด๋ค๋ณด๋ ์์ด๋์ด๋ ์ฝ๊ฒ ์ก์ ์ ์์๋ค.
-
๊ณ์ 6, 7, 8์์ ๋ฐํ์ ์๋ฌ๊ฐ ๋ฐ์ํ๋ค ....
- Enhanced for๋ฌธ ์ฌ์ฉ์ผ๋ก ์ธํ ๋ฐํ์ ์๋ฌ์๋ค๋ ๊ฑธ ์๊ฒ ๋๊ณ .. ์ ๋ฆฌํด์ผ๊ฒ ๋ค.